package geometrie;

import java.util.ArrayList;
import java.util.List;

import scene.Facette3D;


/**
 * This class contains three different implementations of 
 * algorithms to calculate the area of a convex polygon:
 * <li> a Naive recursive which is very inefficient 	 
 * <li> a Recursive using a cache memory to eliminate redundant calculations
 * <li> an iterative which also doesn't have redundant calculations
 * </li>      
 *
 */
public class Rebouchage 
{
	
	private static Cache cache;
	private static List<Facette3D> triangulation;

	/**
	 * This method returns a list of Facette3D corresponding to the polygon to fill the hole that
	 * existed in the polygon that was passed as parameter. This is the recursive algorithm 
	 * using a cache memory. 
	 * @param polygone The polygon to be filled
	 * @return The list of Facette3D filling the hole
	 */
	public static List<Facette3D> rebouchageTrouRecCache(Point[] polygone)
	{
		int i,j,points = polygone.length;
		cache = new Cache(points);
		for (i = 0; i < points; i++)
			for (j = 0; j < points; j++)
				setCache(i, j, -1);
		triangulation = new ArrayList<Facette3D>(points-2);
		cacheTriangulation(0, points-1, polygone);
		getTriangulation(0,points-1,triangulation,polygone);
		return triangulation;
	}
	
	
	private static void getTriangulation(int i, int j, List<Facette3D> triangulation, Point[] polygone) {
		if(j != i+1)
		{
			triangulation.add(new Facette3D(polygone[i],polygone[cache.getMinIndex(i, j)], polygone[j]));
			getTriangulation(i, cache.getMinIndex(i,j), triangulation, polygone);
			getTriangulation(cache.getMinIndex(i,j), j, triangulation, polygone);
		}
		
	}

	/**
	 * This is the effective recursive call for the method rebouchageTrouRecCache 
	 */
	private static double cacheTriangulation(int i, int j, Point[] polygon) 
	{
		if(!isComputed(i,j))
		{
			if(j == i + 1) 
			{
				return 0;
			}
			int k;
			double minimum = Double.MAX_VALUE;
			int minIndex = -1;
			double x;
			for (k = i + 1; k < j; k++) {
				x = cacheTriangulation(i, k, polygon)
						+ cacheTriangulation(k, j, polygon)
						+ area(polygon[i], polygon[k], polygon[j]);
				if(x < minimum)
				{
					minimum = x;
					minIndex = k;
				}
			}
			setCache(i, j, minimum, minIndex);
			return getCache(i, j);
		}
		else
			return getCache(i,j);
	}

	/**
	 * This method returns the area of the polygon that would fill the hole that
	 * exists in the polygon that was passed as parameter using a naive recursive procedure.
	 * @param polygone The polygon to be filled
	 * @return The area of the polygon that would fill the hole that
	 * exists in the polygon that was passed as parameter.
	 */
	public static double rebouchageTrouRecNaif(Point[] polygone) {
		int points = polygone.length;	
		double polygonArea = naiveTriangulation(0, points-1, polygone);
		return polygonArea;
	}
	
	/**
	 * This method returns the area of the polygon that would fill the hole that
	 * exists in the polygon that was passed as parameter.
	 * @param polygone The polygon to be filled
	 * @return The area of the polygon that would fill the hole that
	 * exists in the polygon that was passed as parameter.
	 */
	public static double rebouchageTrouIter(Point[] polygone) {
		int points = polygone.length;
		int i,j,k;
		double x;
		cache = new Cache(points);
		for (i = 0; i < points; i++)
			for (j = 0; j < points; j++)
				setCache(i, j, -1);
		for(j = 1; j < points; j++)
		{ 
			for(i = j-1; i >= 0; i--)
			{
				if(j == i+1)
				{
					setCache(i,j,0);
				}
				else
				{
					double minimum = Double.MAX_VALUE;
					for(k = i+1; k < j; k++)
					{
						x = getCache(i,k) + getCache(k,j) + area(polygone[i],polygone[k],polygone[j]);
						if(x < minimum)
						{
							minimum = x;
						}
					}
					setCache(i,j,minimum);
				}
			}
		}
		return getCache(0,points-1);
	}

	private static double naiveTriangulation(int i, int j, Point[] polygon) {
		if (j == i + 1) {
			return 0;
		}
		if (j == i + 2) {
			return area(polygon[i], polygon[i + 1], polygon[j]);
		} else {
			int k;
			double minimum = Double.MAX_VALUE;
			for (k = i + 1; k < j; k++) {
				minimum = Math.min(
						minimum,
						naiveTriangulation(i, k, polygon)
								+ naiveTriangulation(k, j, polygon)
								+ area(polygon[i], polygon[k], polygon[j]));
			}
			return minimum;
		}
	}

	/*This is the old cache method - it does not calculate the triangulation,
	just the area.*/
	
	/*private static double cacheTriangulation(int i, int j, Point[] polygon) {
		if (!isComputed(i, j)) {
			if (j == i + 1) {
				setCache(i, j, 0);
				return getCache(i, j);
			}
			if (j == i + 2) {
				setCache(i, j, area(polygon[i], polygon[i + 1], polygon[j]));
				return getCache(i, j);
			} else {
				int k;
				double minimum = Double.MAX_VALUE;
				for (k = i + 1; k < j; k++) {
					minimum = Math.min(
							minimum,
							cacheTriangulation(i, k, polygon)
									+ cacheTriangulation(k, j, polygon)
									+ area(polygon[i], polygon[k], polygon[j]));
				}
				setCache(i, j, minimum);
				return getCache(i, j);
			}
		} else {
			return getCache(i, j);

		}

	}*/


	private static boolean isComputed(int i, int j) {
		return !(cache.getValue(i,j) == -1);
	}

	private static void setCache(int i, int j, double value) {
		cache.setValue(i,j,value);
	}
	
	private static void setCache(int i, int j, double value, int minIndex) {
		cache.setValue(i,j,value);
		cache.setMinIndex(i,j,minIndex);
	}

	private static double getCache(int i, int j) {
		return cache.getValue(i,j);
	}

	/**
	 * This method implements the Heron's formula, which calculates the area of any triangle defined by
	 * three vertices p1,p2 and p3.
	 * @param p1 The first vertex
	 * @param p2 The second vertex
	 * @param p3 The third vertex
	 * @return The resulting area
	 */
	private static double area(Point p1, Point p2, Point p3) {
		double a = length(p1, p2);
		double b = length(p2, p3);
		double c = length(p3, p1);
		double p = perimeter(a, b, c) / 2;
		
		return Math.sqrt(p * (p - a) * (p - b) * (p - c));
	}
	
	/**
	 * Calculates the distance between two given points.
	 * @param p1 The first point
	 * @param p2 The second point
	 * @return the distance between the two points
	 */
	private static double length(Point p1, Point p2) {
		return Math.sqrt(Math.pow(p1.getXCartesien() - p2.getXCartesien(), 2)
					   + Math.pow(p1.getYCartesien() - p2.getYCartesien(), 2)
           			   + Math.pow(p1.getZCartesien() - p2.getZCartesien(), 2));
	}

	private static double perimeter(double a, double b, double c) {
		return (a + b + c);
	}	
}

class Cache
{
	private static double[][] value;
	private static int[][] minIndex;
	
	public Cache(int points)
	{
		value = new double[points][points];
		minIndex = new int[points][points];
		int i,j;
		for (i = 0; i < points; i++)
			for (j = 0; j < points; j++)
				{
				value[i][j] = -1; 
				minIndex[i][j] = -1;
				}
	}
	public int getMinIndex(int i, int j) {
		return minIndex[i][j];
	}
	public void setMinIndex(int i, int j, int minIdx) {
		minIndex[i][j] = minIdx;
	}
	public double getValue(int i, int j) {
		return value[i][j];
	}
	public void setValue(int i, int j, double val) {
		value[i][j] = val;
	}	
}